package com.example.heuristicallysearchalgorithm49;

import java.util.LinkedList;
import java.util.List;

/**
 * 启发式搜索算法 查找次优解
 * @auther lijiewei
 * @date 2022/9/26 20:49
 */
public class HeuristicallySearchAlgorithm {

    /**
     * A* 算法，从顶点s到顶点t的路径
     * @return
     * @author lijiewei
     * @date   2022/9/26 20:58
     */
    public void aStar(Graph graph, int s, int t, Node[] nodes) {
        LinkedList<Edge>[] adj = graph.getAdj();
        int count = graph.getV();

        //用来还原最短路径,值存储起点(指向当前节点)的下标
        int[] predecessor = new int[count];
        //按照vertex的f值构建的小顶堆，而不是按照dist
        PriorityQueue queue = new PriorityQueue(count);
        //标记是否进入过队列
        boolean[] inqueue = new boolean[count];

        nodes[s].setDist(0);
        nodes[s].setF(0);
        queue.add(nodes[s]);
        inqueue[s] = true;

        while (!queue.isEmpty()) {
            //取堆顶元素并删除
            Node minNode = queue.poll();
            //与 minNode 相连的边
            List<Edge> edges = adj[minNode.getId()];

            for (int i = 0; i < edges.size(); i++) {
                //取出一条minNode相连的边
                Edge edge = edges.get(i);
                //minNode --> nextNode
                Node nextNode = nodes[edge.tid];
                if (minNode.getDist()+edge.getW() < nextNode.getDist()) {
                    //更新 next 的dist,f
                    nextNode.setDist(minNode.getDist()+edge.getW());
                    nextNode.setF(nextNode.getDist()+hManhattan(nextNode, nodes[t]));
                    predecessor[nextNode.getId()] = minNode.getId();
                    if (inqueue[nextNode.getId()]) {
                        queue.update(nextNode);
                    } else {
                        queue.add(nextNode);
                        inqueue[nextNode.getId()] = true;
                    }
                }

                //只有到达 t 就可以结束 while
                if (nextNode.getId() == t){
                    //情况 queue, 才能推出 while 序号
                    queue.clear();
                    break;
                }

            }
        }

        //输出路径
        System.out.print(s);
        print(s, t, predecessor);
        System.out.println();
    }

    private int hManhattan(Node sNode, Node tNode) {
        return Math.abs(sNode.x-tNode.x)+Math.abs(sNode.y-tNode.y);
    }

    /** 打印. */
    private void print(int s, int t, int[] predecessor) {
        if (s==t) {
            return;
        }
        print(s, predecessor[t], predecessor);
        System.out.print(" -> "+t);
    }
}
